HW#2 --- last modified February 06 2019 04:07:17..

Solution set.

Due date: Mar 6

Files to be submitted:
  Hw2.zip

Purpose: Gain some intuition about the relative hardness of different computational problems

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO2 -- Give a minimal classification of the complexity of a computational problem as being in one of the class L, NL, P, P/poly, NP, coNP, some level of the polynomial hierarchy, PSPACE, E, EXPTIME, decidable, undecidable.

LO3 -- Show the completeness of a complete problem for each of these classes.

Specification:

For this homework I would like you to write up solutions to the problems below. If possible, write up the homework in LaTeX. If you use Word, format any math by using the math equation editor. Once you have prepared your solution output it as a PDF and submit it as Hw2.pdf. Be aware that the maximum-sized document that the upload system supports is 10 MB.

1. Define `2_0 = 1` and `2_{x+1} = 2^(2_x)`. For each of the following functions, show that it is primitive recursive (1/2pt each):
   1. two(x) := 2
   2. mult(x, y) := `x \cdot y`
   3. pow(x) := `2^x`
   4. super_pow(x) := `2_x`
2. Imagine we are performing our `O(T \log T)` universal simulation. This simulation is normally carried out in the alphabet `{0,1, \square, \Delta}`. Expand the alphabet to also include the letters a-z (from class we know this would speed up computations by at lost a constant factor determined by the alphabet size). The simulating machine has 3-read/write tapes. Imagine if the first of these tapes had "computationalcomplexity" written on it and the tape head was reading the letter `x`.
   1. Show a possible state of the simulating tape, indicating the `L_i` and `R_i` zones and tape squares with `\bar{\square}` in them.
   2. Show the next state of the simulating tape, indicating the `L_i` and `R_i` zones and tape squares with `\bar{\square}` in them, if the universal machine moved left and wrote the letter `s`.
3. Recall a boolean circuit is a directed acyclic graph in which:
   1. The nodes of in-degree 0 are inputs. These can be labeled with 0, 1, or a boolean variable `x_i` for `1 \leq i \leq n`.
   2. Nodes other than the inputs have max in-degree 2. Input nodes If the in-degree is 2, a node must be labeled either `\vee` or `\wedge`. If the in-degree is 1, it must be labeled `\neg`.
   3. The nodes of out-degree 0 are the outputs.
   4. Given an assignment `\nu: x_i mapsto {0,1}` for each of the variables, the output of each node in the circuit can be determined by propagating the input values through the gates according to the usual rules for `\vee`, `\wedge`, and `\neg`.
   5. The output of a circuit is the output of out-degree `0` gates. For this exercise assume there is one such gate.
   For each of the following problems determine the smallest complexity class it belongs to among `P`, `NP`, `coNP`, `EXP` and give an argument as to why (1/2pt each).
   1. Given an encoding of a circuit and an encoding of an assignment to its variables, determine its output value.
   2. Given encodings of two circuits `C_1` and `C_2` determine if all assignments which make `C_1` output 1 make `C_2` output 1.
   3. Given an encoding of a circuit determine and a number `k` determine if the circuit has at least `k` assignments which make it output 1.
   4. Given an encoding of a circuit determine and a number `k` determine if the circuit has exactly `k` assignments which make it output 1.
4. Define `NQLIN = \cup_k NTIME(nlog^k n)` (nondeterministic quasi-linear time). It turns out this class shares many characteristics with `NP`. Call a reduction quasi-linear if it runs on inputs of length `n` in time `n \log^k n` for some fixed `k`. Show that `TMSAT` from class is complete for `NQLIN` under quasi-linear time reductions.
5. Pick an NP-complete problem from Wikipedia's List of NP-complete Problems that was not covered in class, and that you think is cool. You are not allowed to pick one you think is not cool. For that problem, look up there reference on Wikipedia as to why it is NP-complete and summarize the argument from that paper (at most 1 page summary).

Point Breakdown